#include <vector>
#include <algorithm>
#include <string>
#include <iostream>
#include <cstdlib>
#include <unistd.h>
#include <sys/time.h>

using namespace std;

const int defaultSize = 10000;
typedef int T;
const T T0 = 0;
const string tsep = "  |  ";

static class Chrono {
    private:
        double start_time;
    public:
        static double get_time() {
            struct timeval tp;
            struct timezone tzp;
            gettimeofday(&tp, &tzp);
            return ((double)tp.tv_sec+(1.e-6)*tp.tv_usec);
        }
        void start() { start_time = get_time();}
        double time() { return get_time() - start_time;}
        Chrono() { start(); }
} chrono;


int main(int na, char** arg) {
	unsigned int size;
	if(na > 1) size = atoi(arg[1]); else size = defaultSize;
	cout << "Benchmarking C-array VS std-vector:" << endl;
	int local = 1 + (size >> 3);
	const int localRepeat = 1000;
	
	cout << "Linear " << size << endl;
	{
		cout << "\tAllocating..." << endl;
		T* a = new T[size];
		vector<T> v(size);
		cout << "\tFill... ";
		chrono.start();
		for(int i = 0; i < size; i++) a[i] = T0;
		cout << "\t" << chrono.time() << tsep;
		chrono.start();
		fill(v.begin(), v.end(), T0);
		cout << chrono.time() << endl;
		cout << "\tChanging... ";
		chrono.start();
		for(int i = 0; i < size; i++) a[i]++;
		cout << "\t" << chrono.time() << tsep;
		chrono.start();
		for(vector<T>::iterator i = v.begin(); i != v.end(); i++) (*i)++;
		cout << chrono.time() << endl;
		cout << "\tNeighbourhood scan... ";
		int x0[localRepeat];
		for(int r = 0; r < localRepeat; r++) x0[r] = rand() % size;
		chrono.start();
		for(int r = 0; r < localRepeat; r++) {
			int s = 0;
			for(int dx = x0[r] - local; dx <= x0[r] + local; dx++) s+= a[dx % size];
		}
		cout << "\t" << chrono.time() << tsep;
		chrono.start();
		for(int r = 0; r < localRepeat; r++) {
			int s = 0;
			for(int dx = x0[r] - local; dx <= x0[r] + local; dx++) s+= v[dx % size];
		}
		cout << chrono.time() << endl;
		cout << "\tReleasing..." << endl;
		delete[] a;
	}
	
	cout << "2D " << size << " x " << size << endl;
	local = 1 + (local >> 3);
	{
		cout << "\tAllocating..." << endl;
		int size2 = size * size;
		T* a = new T[size2];
		vector< vector<T> > v(size);
		for(int i = 0; i < size; i++) v[i].resize(size);
		cout << "\tFill... ";
		chrono.start();
		for(int i = 0; i < size2; i++) a[i] = T0;
		cout << "\t" << chrono.time() << tsep;
		chrono.start();
		for(vector<vector<T> >::iterator x = v.begin(); x != v.end(); x++) for(vector<T>::iterator y = (*x).begin(); y != (*x).end(); y++) *y = T0;
		cout << chrono.time() << endl;
		cout << "\tChanging... ";
		chrono.start();
		for(int i = 0; i < size2; i++) a[i]++;
		cout << "\t" << chrono.time() << tsep;
		chrono.start();
		for(vector<vector<T> >::iterator x = v.begin(); x != v.end(); x++) for(vector<T>::iterator y = (*x).begin(); y != (*x).end(); y++) *y++;
		cout << chrono.time() << endl;
		cout << "\tNeighbourhood scan... ";
		int x0[localRepeat];
		int y0[localRepeat];
		for(int r = 0; r < localRepeat; r++) { x0[r] = rand() % size; y0[r] = rand() % size; }
		chrono.start();
		for(int r = 0; r < localRepeat; r++) {
			int s = 0;
			for(int dx = x0[r] - local; dx <= x0[r] + local; dx++) {
				T* line = a + (dx % size) * size;
				for(int dy = y0[r] - local; dy <= y0[r] + local; dy++) s+= line[dy % size];
			}
		}
		cout << "\t" << chrono.time() << tsep;
		chrono.start();
		for(int r = 0; r < localRepeat; r++) {
			int s = 0;
			for(int dx = x0[r] - local; dx <= x0[r] + local; dx++) {
				vector<T> line = v[dx % size];
				for(int dy = y0[r] - local; dy <= y0[r] + local; dy++) s += line[dx % size];
			}
		}
		cout << chrono.time() << endl;
		cout << "\tReleasing..." << endl;
		delete[] a;
	}
	
	return 0;
}
